package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

/**
 * 冒泡排序
 */
public class BubbleSort {

    /**
     * 重复地走访过要排序的数列，一次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来
     * 每排序一趟至少可以确定一个最大数或最小数
     * 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
     * 默认由小到大排序
     * @param array 原数组，执行完后数组内容改变
     */
    public static void bubbleSort(int[] array) {
        ArrayUtils.printArray(array, 0);
        // 最多排序 (array.length - 1) 趟
        for (int i = 1; i < array.length; i++) {
            //判断该趟是否发生交换
            boolean isExchange = false;
            for (int j = 0; j < array.length - i; j++) {
                // 每排序一趟会将当前最大值移动到最后
                // 每排序一趟下一趟排序最大交换次数会减少1
                if (array[j] > array[j + 1]) {
                    // 依次比较相邻的元素
                    ArrayUtils.swap(array, j, j + 1);
                    if (!isExchange) {
                        isExchange = true;
                    }
                }
            }
            ArrayUtils.printArray(array, i);
            // 若该趟没有交换则排序完成
            if (!isExchange) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        bubbleSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        bubbleSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        bubbleSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }
}
